Теорема Эрдёша — Секереша

Цепь из четырёх рёбер с положительным наклоном на множестве из 17 точек. Если образовать последовательность y-координат этих точек, в порядке их x-координат, теорема Эрдёша — Секереша гарантирует, что существует либо цепь такого типа, либо цепь той же длины, в которой все наклоны отрицательны. Однако, если центральная точка отсутствует, такая цепь не существовала бы.

Теорема Э́рдёша — Се́кереша в комбинаторике — утверждение, уточняющее одно из следствий теоремы Рамсея для финитного случая. В то время как теорема Рамсея облегчает доказательство того, что каждая последовательность разных действительных чисел содержит монотонно возрастающую бесконечную подпоследовательность или монотонно убывающую бесконечную подпоследовательность, результат, доказанный Палом Эрдёшем и Дьёрдем Секерешем, идёт дальше. Для данных $r$, $s$ они показали, что любая последовательность разных чисел длины не менее $(r-1)(s-1)$ содержит монотонно возрастающую подпоследовательность длины $r$ или монотонно убывающую длины $s$. Доказательство появилось в той же самой работе 1935 года, что и задача со счастливым концом.

Пример

Для $r=3$ и $s=2$, теорема говорит, что любая перестановка трёх чисел имеет возрастающую подпоследовательность длиной три или убывающую подпоследовательность длиной два. Из шести перестановок чисел 1, 2, 3:

• 123 имеет возрастающую подпоследовательность длиной три;
• 132 имеет убывающую подпоследовательность 32;
• 213 имеет убывающую подпоследовательность 21;
• 231 имеет две убывающие подпоследовательности: 21 и 31;
• 312 имеет две убывающие подпоследовательности: 31 и 32;
• 321 имеет три убывающие подпоследовательности длины два: 32, 31, и 21.

Геометрическая интерпретация

Позиции чисел в последовательности можно интерпретировать как $x$-координаты точек в евклидовой плоскости, а сами числа как $y$-координаты; с другой стороны, для любого множества точек на плоскости их $y$-координаты, упорядоченные по их $x$-координатам, образуют последовательность чисел (если только два числа не имеют двух одинаковых $x$-координат). При такой связи между последовательностями и множествами точек теорему Эрдёша — Секереша можно интерпретировать как утверждение, что для любого множества из $rs+1$ или более точек найдётся ломаная из $r$ положительно наклоненных отрезков или из $s$ отрезков с отрицательным наклоном. Например, при $r=s=4$ любое множество из 17 или более точек имеет цепь из четырёх рёбер, в котором все наклоны имеют одинаковый знак.

Доказательство

Теорема Эрдёша — Секереша может быть доказана несколькими разными способами. Майкл Стил дает обзор шести разных доказательств теоремы, в том числе с использованием принципа Дирихле и теоремы Дилуорса. Прочие способы доказательства, приводимые Стилом, включают оригинальное доказательство Эрдёша и Секереша и доказательство Блэквелла, Ловаса и самого Стила.Доказательство также есть в книге.

Доказательство через принцип Дирихле

Основная статья: Принцип Дирихле

В последовательности длины $(r-1)(s-1)+1$ пометим каждое число $n_{i}$ парой $(a_{i},b_{i})$, где $a_{i}$ — длина наибольшей монотонно возрастающей подпоследовательности, заканчивающейся на $n_{i}$, $b_{i}$ длина наибольшей монотонно убывающей подпоследовательности, заканчивающейся на $n_{i}$. Все числа в последовательности помечены различными парами: если $i<j$ и $n_{i}\leq n_{j}$, то $a_{i}<a_{j}$; если $n_{i}\geq n_{j}$, то $b_{i}<b_{j}$. Но есть всего $(r-1)(s-1)$ возможных пар, если $a_{i}\leq r-1$, а $b_{i}\leq s-1$, так что по принципу Дирихле существует $i$, для которого $a_{i}$ или $b_{i}$ выходит за пределы этого ограничения. Если $a_{i}$ выходит за пределы, то $n_{i}$ — часть возрастающей подпоследовательности длины не меньше $r$, если $b_{i}$ выходит за пределы, то $n_{i}$ — часть убывающей подпоследовательности длины не меньше $s$.

См. также

• Задача поиска наибольшей увеличивающейся подпоследовательности

Источники

• Weisstein, Eric W. Erdős-Szekeres Theorem (англ.) на сайте Wolfram MathWorld.

Литература

• Айгнер М. Комбинаторная теория. — М.: Мир, 1982. — 555 с.